package date422;

public class Solution {
	public static void main(String[] args) {
		Solution solution = new Solution();

		// System.out.println(solution.NumberOf2(5));
		System.out.println(solution.Power(2, -3));
	}

	/*
	 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。
	 */
	public int JumpFloorII(int target) {
		/*
		 * 1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。 2）n = 1时，只有1种跳法，f(1) = 1 3) n =
		 * 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)  4) n =
		 * 3时，会有三种跳得方式，1阶、2阶、3阶，
		 *     那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
		 *     因此结论是f(3) = f(3-1)+f(3-2)+f(3-3) 5) n =
		 * n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：     f(n) = f(n-1)+f(n-2)+...+f(n-(n-1))
		 * + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) 6)
		 * 由以上已经是一种结论，但是为了简单，我们可以继续简化：     f(n-1) = f(0) + f(1)+f(2)+f(3) + ...
		 * + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)     f(n) =
		 * f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
		 *     可以得出：     f(n) = 2*f(n-1) 7)
		 * 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
		 * 
		 *               | 1       ,(n=0 )  f(n) =     | 1       ,(n=1 )
		 * 
		 *               | 2*f(n-1),(n>=2)
		 */
		if (target == 1) {
			return 1;
		} else if (target <= 0) {
			return -1;
		} else {
			return 2 * JumpFloorII(target - 1);
		}
	}

	/*
	 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
	 */
	public int RectCover(int target) {
		if (target == 0) {
			return 0;
		}
		if (target == 1) {
			return 1;
		}
		int arr[] = new int[target + 1];
		arr[0] = 1;
		arr[1] = 1;
		for (int i = 2; i < arr.length; i++) {
			arr[i] = arr[i - 1] + arr[i - 2];
		}

		return arr[target];

	}

	/*
	 * 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
	 */
	public int NumberOf1(int n) {
		int count = 0;
		int flag = 1;
		while (flag != 0) {
			if ((n & flag) != 0) {
				count++;
			}
			flag = flag << 1;
		}
		return count;
	}

	public int NumberOf2(int n) {
		int count = 0;

		while (n != 0) {
			count++;
			n = n & (n - 1);
			System.out.println("--," + n);
		}
		return count;
	}

	/*
	 * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
	 */
	public double Power(double base, int exponent) {
		double b = base;
		double p = 1 / base;
		if (exponent > 0) {
			for (int i = 0; i < exponent - 1; i++) {
				base = base * b;
			}
		} else if (exponent == 0) {
			return 1;
		} else {
			base = p;
			for (int i = exponent; i < -1; i++) {
				base = base * p;
			}
		}

		return base;
	}

}
